|
In computer science, the readers-writers problems are examples of a common computing problem in concurrency. There are at least three variations of the problems, which deal with situations in which many threads try to access the same shared resource at one time. Some threads may read and some may write, with the constraint that no process may access the share for either reading or writing, while another process is in the act of writing to it. (In particular, it ''is'' allowed for two or more readers to access the share at the same time.) A readers-writer lock is a data structure that solves one or more of the readers-writers problems. The basic reader-writers problem was first formulated and solved by Courtois ''et al.'' ==First readers-writers problem== Suppose we have a shared memory area with the basic constraints detailed above. It is possible to protect the shared data behind a mutual exclusion mutex, in which case no two threads can access the data at the same time. However, this solution is suboptimal, because it is possible that a reader ''R1'' might have the lock, and then another reader ''R2'' requests access. It would be foolish for ''R2'' to wait until ''R1'' was done before starting its own read operation; instead, ''R2'' should start right away. This is the motivation for the first readers-writers problem, in which the constraint is added that ''no reader shall be kept waiting if the share is currently opened for reading.'' This is also called readers-preference, with its solution: semaphore resource=1; semaphore mutex=1; readcount=0; / * Please note that: resource.P() is equivalent to wait(resource) resource.V() is equivalent to signal(resource) mutex.P() is equivalent to wait(mutex) mutex.V() is equivalent to signal(mutex) */ writer() reader() In this solution of the readers/writers problem, the first reader must lock the resource(shared file) if such is available. Once the file is locked from writers, it may be used by many subsequent readers without having them to re-lock it again. Before entering the CS, every new reader must go through the entry section. However, there may only be a single reader in the entry section at a time. This is done to avoid race conditions on the readers (e.g. two readers increment the readcount at the same time, and both try to lock the resource, causing one reader to block). To accomplish this, every reader which enters the Once the first reader is in the entry section, it will lock the resource. Doing this will prevent any writers from accessing it. Subsequent readers can just utilize the locked (from writers) resource. The very last reader (indicated by the readcount variable) must unlock the resource, thus making it available to writers. In this solution, every writer must claim the resource individually. This means that a stream of readers can subsequently lock all potential writers out and starve them. This is so, because after the first reader locks the resource, no writer can lock it, before it gets released. And it will only be released by the very last reader. Hence, this solution does not satisfy fairness. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Readers–writers problem」の詳細全文を読む スポンサード リンク
|